//https://leetcode.cn/problems/number-of-ways-to-arrive-at-destination/description/?envType=daily-question&envId=2024-03-05

using ll = long long;

class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        const int mod = 1e9 + 7;
        vector<vector<pair<int, int>>> g(n);
        for (auto& road : roads) {
            g[road[0]].emplace_back(road[1], road[2]);
            g[road[1]].emplace_back(road[0], road[2]);
        }

        vector<ll> dist(n, numeric_limits<ll>::max());
        vector<int> cnt(n, 0), vis(n);
        dist[0] = 0;
        cnt[0] = 1;
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        pq.emplace(0, 0);

        while (!pq.empty()) {
            auto [curr_dist, u] = pq.top();
            pq.pop();
            
            if (vis[u]) continue;

            vis[u] = true;

            for (auto& [v, time] : g[u]) {
                if (curr_dist + time < dist[v]) {
                    dist[v] = curr_dist + time;
                    cnt[v] = cnt[u];
                    pq.emplace(dist[v], v);
                } else if (curr_dist + time == dist[v]) {
                    cnt[v] = (cnt[v] + cnt[u]) % mod;
                }
            }
        }

        return cnt[n - 1];
    }
};